package com.tarry.stack;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * 顺序栈：使用数组来实现栈的操作
 * <br>
 * <p>
 *     时间复杂度 O(n)
 *     空间复杂度 O(n)
 * </p>
 */
@Slf4j
public class ArrayStack {
    // 栈元素
    private String[] element;
    // 栈数组容量
    private int capacity;
    // 栈指针位置
    private int index;

    public ArrayStack(int capacity){
        this.element = new String[capacity];
        this.capacity = capacity;
        this.index = 0;
    }

    /**
     * 如栈操作
     * @param item
     * @return
     */
    public boolean push(String item){
        // 如栈时，需要判断栈容量是否已经使用完
//        if (this.capacity == this.index) {
//            log.warn("The Stack is full !");
//            return false;
//        }

        // 对栈进行动态扩容,仅在栈满时，如栈操作会进行数组复制，均摊时间复杂度为 O(1)
        if (this.capacity == this.index) {
            int newCapacity = this.capacity << 1;
            this.capacity = newCapacity;
            log.info("the new capacity is {}",newCapacity);
           this.element = Arrays.copyOf(this.element,newCapacity);
        }
        this.element[this.index] = item;
        this.index ++;
        return true;
    }

    /**
     * 出栈操作
     * @return
     */
    public String pop(){
        // 出栈时，需要判断栈中是否还有元素
        if (this.index == 0) {
            throw new RuntimeException("The stack is empty !");
        }
        // 如栈后栈指针移位到下一个元素位，因此出栈时栈顶下标为 index-1
        String tmp = this.element[this.index - 1];
        this.index --;
        return tmp;
    }

    public void showItems(){
        if (this.index == 0) {
            log.warn("The stack is empty");
            return;
        }
        for (int i = this.index - 1; i >= 0; i--) {
            System.out.println("item["+(i+1)+"] = " + this.element[i]);
        }
    }

}
